// class Solution {
//     /*
//         摩尔计数法：
//         这就相当于每个“多数元素”和其他元素 两两相互抵消，
//         抵消到最后肯定还剩余至少1个“多数元素”。
//     */
//     public int majorityElement(int[] nums) {
//         int count = 0;
//         int res = nums[0];
//         for(int i : nums){
//             if(count==0){
//                 res = i;
//             }
//             if( i==res ) 
//                 count++;
//             else 
//                 count--;
//         }
//         return res;
//     }
// }
class Solution {
    /*
        摩尔计数法：
        这就相当于每个“多数元素”和其他元素 两两相互抵消，
        抵消到最后肯定还剩余至少1个“多数元素”。
    */
    public int majorityElement(int[] nums) {
        int count = 0;
        int res = nums[0]; // 候选人
        for(int i : nums){
            if(count==0){ // count为0就要选择新的候选人
                res = i;
                count ++;
            }else if( res==i ){ //候选人加一票
                count++;
            }else{              //选的不是候选人，冲突了
                count--;  
            }
        }
        return res;
    }
}
class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length/2];
    }
}